This disclosure relates to computer-generated imagery (CGI) and computer-aided animation. More specifically, this disclosure relates to techniques for tetrahedral shell generation for use in CGI and computer-aided animation.
With the wide-spread availability of computers, computer graphics artists and animators can rely upon computers to assist in production process for creating animations and computer-generated imagery (CGI). This may include using computers to have physical models be represented by virtual models in computer memory. Typically, two-dimensional (2D) or three-dimensional (3D) computer-aided animation combines 2D/3D models of objects and programmed movement of one or more of the models. In 3D computer animation, the first step is typically the object modeling process. Objects can be sculpted much like real clay or plaster, working from general forms to specific details, for example, with various sculpting tools. Models may then be constructed, for example, out of geometrical vertices, faces, and edges in a 3D coordinate system to represent the objects. These virtual models can then be manipulated using computers to, for example, simulate physics, design aesthetic actions such as poses or other deformations, crate lighting, coloring and paint, or the like, of characters or other elements of a computer animation display.
Pixar is one of the pioneering companies in the computer-generated imagery (CGI) and computer-aided animation industry. Pixar is more widely known as Pixar Animation Studios, the creators of animated features such as “Toy Story” (1995) and “Toy Story 2” (1999), “A Bugs Life” (1998), “Monsters, Inc.” (2001), “Finding Nemo” (2003), “The Incredibles” (2004), “Cars” (2006), “Ratatouille” (2007), and others. In addition to creating animated features, Pixar develops computing platforms and tools specially designed for computer-aided animation and CGI. One such example is now known as PhotoRealistic RenderMan, or PRMan for short. PRMan is a photorealistic RenderMan-compliant rendering software system based on the RenderMan Interface Specification (RISpec) which is Pixar's technical specification for a standard communications protocol (or interface) between 3D computer graphics programs and rendering programs. PRMan is produced by Pixar and used to render their in-house 3D animated movie productions. It is also available as a commercial product licensed to third parties, sold as part of a bundle called RenderMan Pro Server, a RenderMan-compliant rendering software system developed by Pixar based on their own interface specification. Other examples include tools and plug-ins for programs such as the AUTODESK MAYA high-end 3D computer graphics software package from AutoDesk, Inc. of San Rafael, Calif.
One core functional aspect of PRMan can include the use of a “rendering engine” to convert geometric and/or mathematical descriptions of objects into images. This process is known in the industry as “rendering.” For movies, other animated features, shorts, and special effects, a user (e.g., a skilled computer graphics artist) can specify the geometric or mathematical description of objects to be used in the rendered image or animation sequence, such as characters, props, background, or the like. In some instances, the geometric description of the objects may include a number of animation control variables (avars) and values for the avars. An animator may also pose the objects within the image or sequence and specify motions and positions of the objects over time to create an animation.
As such, the production of CGI and computer-aided animation may involve the extensive use of various computer graphics techniques to produce a visually appealing image from the geometric description of an object that may be used to convey an essential element of a story or provide a desired special effect. One of the challenges in creating these visually appealing images can be the balancing of a desire for a highly-detailed image of a character or other object with the practical issues involved in allocating the resources (both human and computational) required to produce those visually appealing images.
Efficient collision detection is a fundamental problem in physically-based simulation and in computer animation. In order to accelerate collision detection for rigid bodies, many approaches based on pre-computed bounding-volume hierarchies have been proposed. However, in cases of deformable objects, these hierarchical data structures cannot be pre-computed, but have to be updated frequently. Although effort has been spent to optimize this update, it is still expensive in case of dynamic environments.
Although not necessarily confined to triangular meshes, generating a water-tight shell volume around a surface is necessary for certain types of collision detection. Tetrahedra are good primitives to represent this volume because of their ease of performing geometric tests such as intersection with other geometric primitives.
Typically, each triangular face of a triangulated surface mesh is extruded into a prism. That prism is then filled with tetraheda (tets). At minimum, there are 3 tets required to fill each prism. To ensure the surface is water-tight (no gaps between prisms), adjacent prism faces (quads) must be split into two tet-faces such that the tet-faces match up.
Accordingly, what is desired is to solve one or more of the problems relating to tetrahedral shell generation for use in CGI and computer-aided animation, some of which may be discussed herein. Additionally, what is desired is to reduce some of the drawbacks relating to tetrahedral shell generation for use in CGI and computer-aided animation, some of which may be discussed herein.